home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 11696 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.5 KB

  1. Path: keats.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: REQUEST: Recursive functions
  5. Date: 25 Mar 1996 13:18:41 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4j72jhINNp77@keats.ugrad.cs.ubc.ca>
  8. References: <4h7lft$8ql@cis.clark.edu> <3150334B.1802@willows.com> <827630695snz@genesis.demon.co.uk> <1996Mar25.125041.116595@kuhub.cc.ukans.edu>
  9. NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
  10.  
  11. In article <1996Mar25.125041.116595@kuhub.cc.ukans.edu>,
  12.  <anh@kuhub.cc.ukans.edu> wrote:
  13.  >A classic way to find one's way through a 2D maze is to always keep to the 
  14.  >right.  In other words, if you arrive at an intersection, turn right, 
  15.  >eventually you will find your way out.  Now if your maze's only exit is 
  16.  >the entrance you will come back to the entrance after you have visited 
  17.  >the whole maze, and, hence, you must have encountered the cheese on the 
  18.  >way.  If there are multiple exits, well, just make sure you mark the 
  19.  >entrance to know when to quit searching.
  20.  
  21. False. You will visit the whole maze if it is isomorphic to a connected,
  22. acyclic graph.  Then, the search you describe is basically a depth-first
  23. traversal.
  24.  
  25. If the maze has cycles, you will end up not visiting some of the cells. You
  26. might not even find your way out, if the starting point is in the centre, and
  27. the rule of keeping to the right forces you to follow a wall that is surrounded
  28. by a loop.
  29. -- 
  30.  
  31.